package arithmetic;

import arithmetic2.TreeNode;

/**
 * @Author: Jie
 * @Date: 2019/1/22 14:17
 * @Function :二叉树 最近祖先leetcode 235/236
 *
 * 百度百科中最近公共祖先的定义为：235 236
 * “对于有根树 T 的两个结点 p、q，
 * 最近公共祖先表示为一个结点 x，
 * 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 * 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class A_10_LowestCommonAncestor {
    /**
     * 打印形状
     *       6
     *     5    8
     *   2  6  7  11
     *-10 3         15
     * @param args
     */
    public static void main(String[] args) {
        TreeNode tr1 = new TreeNode(6);
        TreeNode tr2 = new TreeNode(5);
        TreeNode tr3 = new TreeNode(8);
        tr1.left=tr2;
        tr1.right=tr3;
        TreeNode tr4 = new TreeNode(2);
        TreeNode tr5 = new TreeNode(6);
        tr2.left=tr4;
        tr2.right=tr5;
        TreeNode tr6 = new TreeNode(7);
        TreeNode tr7 = new TreeNode(11);
		    tr3.left=tr6;
		    tr3.right=tr7;
        TreeNode tr8 = new TreeNode(15);
        tr7.right=tr8;
        TreeNode tr9 = new TreeNode(-10);
        TreeNode tr10 = new TreeNode(3);
        tr4.left=tr9;
        tr4.right=tr10;

        System.out.println(lowestCommonAncestor(tr1,tr4,tr9).val);
    }

    /**
     * 236 递归实现 ，无序树
     * 思路，O ( n )
     *
     * 1.寻找 p q,找到就 return
     * 2.left right 分别遍历，
     * 3.左树 不存在 p or q，肯定在右树
     * 4.找到 null 或者 p  或者 q return
     * 5.在 左树 右树都有 p 或者 q, 那么root 肯定是根节点。
     *
     * 如果只找到p ,那么证明 q是p 的子节点。
     *
     * root == p
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {//找到 终点，或者 p  q
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left == null) {//左树 ,不存在 p or q，肯定在右树
            return right;
        }
        if (right == null) {//right tree not have, must leftTree have p or q.
            return left;
        }
        return root;//在 左树 右树都有 p 或者 q, 那么root 肯定是根节点。

    }

    //235 10 ms 二叉搜索树，有序
    public static TreeNode lowestCommonAncestorBinarySearchTree(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return root;
        }
        while (root !=null) {
            if (p.val < root.val && q.val < root.val) { //p q 都在root 左边
                root = root.left;
            }else if (q.val > root.val && p.val > root.val) {//p q 都在root 右边
                root = root.right;
            }else {
                return root;//分叉 或者一个为根节点。
            }
        }
        return root;
    }

    //235 二叉搜索数，递归 11ms 比非递归 时间长
    public static TreeNode lowestCommonAncestorBinarySearchTreeRecursion(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return root;
        }
        if (p.val < root.val && q.val < root.val) { //p q 都在root 左边
            return lowestCommonAncestorBinarySearchTreeRecursion(root.left, p, q);
        }
        if (q.val > root.val && p.val > root.val) {//p q 都在root 右边
            return lowestCommonAncestorBinarySearchTreeRecursion(root.right, p, q);
        }
        return root;//分叉 或者一个为根节点。
    }
}
